package twopointer;

import java.util.Arrays;

/**
 * 验证有效的三角形
 * https://leetcode-cn.com/problems/valid-triangle-number/
 */
public class TriangleNumber {

    public static void main(String[] args) {
        int[] nums = {2,2,3,4};
        System.out.println(new TriangleNumber().triangleNumber(nums));
    }

    /**
     * 双指针解法
     * 三角形：两边之和大于第三边；只需要判断 a + b > c
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int total = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0;
            int right  = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    total += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
        }
        return total;
    }

}
